package cn.hycat.leetcode.middle;

import java.util.Stack;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
/*      单调栈
        给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

        示例 1:

        输入: temperatures = [73,74,75,71,69,72,76,73]
        输出: [1,1,4,2,1,1,0,0]
        示例 2:

        输入: temperatures = [30,40,50,60]
        输出: [1,1,1,0]
        示例 3:

        输入: temperatures = [30,60,90]
        输出: [1,1,0]

        1 <= temperatures.length <= 105
        30 <= temperatures[i] <= 100*/
public class L739每日温度 {
    public static void main(String[] args) {
        int[] temperatures = {73,74,75,71,69,72,76,73};
        print(dailyTemperatures(temperatures));
    }

    public static int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> s = new Stack();
        int[] res = new int[temperatures.length];
        for(int i = 0; i <temperatures.length; i++) {
            while(!s.isEmpty() && temperatures[i] > temperatures[s.peek()]) {
                Integer pop = s.pop();
                res[pop] = i - pop;
            }
            s.push(i);
        }
        return res;
    }

    public static void print(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}
